За­ну­ме­ру­ем клет­ки как по­ка­за­но на ри­сун­ке 1. Конь может из любой клет­ки по­пасть в любую клет­ку с таким же но­ме­ром, и не может по­пасть в дру­гие.

Таким об­ра­зом, все клет­ки раз­би­лись на 4 мно­же­ства, так что конь не может пе­ре­ско­чить из од­но­го мно­же­ства в дру­гое, но может сво­бод­но пе­ре­ме­щать­ся внут­ри од­но­го мно­же­ства.

До­ба­вим две клет­ки как на ри­сун­ке 2. До­ка­жем, что те­перь конь может по­пасть из любой клет­ки в любую дру­гую. Клет­ка А со­еди­ня­ет клет­ки, от­ме­чен­ные ро­зо­вым цве­том, т. е. через ней можно из мно­же­ства 1 пе­ре­ско­чить в мно­же­ство 4. (На­хо­дясь в любой клет­ке с но­ме­ром 1, можно прий­ти в ро­зо­вую клет­ку с но­ме­ром 1, затем через A по­пасть в ро­зо­вую клет­ку с но­ме­ром 4, и из ней в любую клет­ку с но­ме­ром 4. В итоге из любой клет­ки с но­ме­ром 1 можно с по­мо­щью А по­пасть в любую клет­ку с но­ме­ром 4.)

Клет­ка В со­еди­ня­ет клет­ки, от­ме­чен­ные зелёным, т. е. через ней можно из лю­бо­го из мно­жеств 2, 3, 4 пе­ре­ско­чить так же в любое из этих мно­жеств.

В итоге, со­че­тая клет­ки A, B, можно из лю­бо­го мно­же­ства по­пасть в любое дру­гое. На­при­мер чтобы по­пасть из мно­же­ства 1 в мно­же­ство 2, вна­ча­ле с по­мо­щью А по­па­да­ем из 1 в 4, затем с по­мо­щью В по­па­да­ем из 4 в 2.

Оста­лось убе­дить­ся, что одной клет­ки не хва­тит. Из ри­сун­ка 3 видно, что все до­бав­ля­е­мые клет­ки раз­би­ва­ют­ся на два вида: в клет­ки А можно по­пасть не боль­ше чем из 3 кле­ток доски, в клет­ки В можно по­пасть из 4-х кле­ток, но среди них все­гда есть две из од­но­го мно­же­ства (от­ме­чен­ные оди­на­ко­вой циф­рой). Т. е. клет­ки, в ко­то­рую можно по­пасть из всех 4-х мно­жеств, не су­ще­ству­ет.

Ответ: 2.

Чтобы можно было од­но­знач­но опре­де­лить, в какой из 100 ко­ро­бок лежит приз, тре­бу­ет­ся воз­мож­ность по­лу­чить хотя бы 100 раз­лич­ных от­ве­тов на один набор во­про­сов. Так как от­ве­ты ве­ду­ще­го для раз­лич­ных по­ло­же­ний приза могут от­ли­чать­ся толь­ко чис­лом "да" среди них, то тре­бу­ет­ся воз­мож­ность по­лу­чить в ответ хотя бы 100 раз­лич­ных ко­ли­честв "да". Зна­чит, тре­бу­ет­ся хотя бы 99 во­про­сов (от 0 до 99 "да" ). При­мер на 99 во­про­сов. Пусть k-ый во­прос: «Номер ко­роб­ки, в ко­то­рой лежит приз, мень­ше либо равен k?». Тогда если от­ве­тов "да" ноль, то приз в сотой ко­роб­ке, если один, то в 99-й и т. д.

Ответ: 99.

Чтобы можно было од­но­знач­но опре­де­лить, в какой из 100 ко­ро­бок лежит приз, тре­бу­ет­ся воз­мож­ность по­лу­чить хотя бы 100 раз­лич­ных от­ве­тов на один набор во­про­сов. Так как от­ве­ты ве­ду­ще­го для раз­лич­ных по­ло­же­ний приза могут от­ли­чать­ся толь­ко чис­лом "да" среди них, то тре­бу­ет­ся воз­мож­ность по­лу­чить в ответ хотя бы 100 раз­лич­ных ко­ли­честв "да". Зна­чит, тре­бу­ет­ся хотя бы 99 во­про­сов (от 0 до 99 "да"). При­мер на 99 во­про­сов. Пусть k-ый во­прос: «Номер ко­роб­ки, в ко­то­рой лежит приз, мень­ше либо равен k?». Тогда если от­ве­тов "да" ноль, то приз в сотой ко­роб­ке, если один, то в 99-й и т. д.

Ответ: 99.

Пусть p_n  — при­быль фирмы ранга n. Тогда по усло­вию за­да­чи

За­ме­тим, что для лю­бо­го n

До­ка­жем, что

Ис­поль­зу­ем метод ма­те­ма­ти­че­ской ин­дук­ции.

1)  База ин­дук­ции:

2)  Ин­дук­ци­он­ный пе­ре­ход: пусть До­ка­жем, что

Дей­стви­тель­но,

Сле­до­ва­тель­но,

Для того, чтобы фирма имела при­быль рав­ную 2016 д. е., её ранг дол­жен удо­вле­тво­рять ра­вен­ству

По­след­нее урав­не­ние имеет на­ту­раль­ное ре­ше­ние n = 63.

Ответ: да, это ранг рав­ный 63.

Не­об­хо­ди­мо по­ка­зать ас­со­ци­а­тив­ность опе­ра­ции для трёх про­из­воль­ных a, b, c, а затем про­ве­сти вы­чис­ле­ние, за­ме­тив, что на каж­дом шаге по­лу­ча­ет­ся вы­ра­же­ние вида

Ответ: (1 + 1)(1 + 1/2) . . . (1 + 1/100) − 1  =  101 − 1  =  100.

При­ведём вы­иг­рыш­ную стра­те­гию для Да­ни­лы. Число кле­ток на по­верх­но­сти чётно (равно ). Разобьём всю по­верх­ность куба на до­ми­нош­ки; до­ми­нош­ки не пе­ре­се­ка­ют­ся и по­кры­ва­ют весь куб. При­мер раз­би­е­ния при­во­дить не будем. Легко ви­деть, что такие при­ме­ры есть. Школь­ни­ки, ко­то­рые на­пи­са­ли такое ре­ше­ние долж­ны при­во­дить при­мер.

В на­ча­ле хода Да­ни­лы пешка стоит в какой-то до­ми­нош­ке. Да­ни­ла ходит во вто­рую клет­ку до­ми­нош­ки. Если Да­ни­ла до этого дей­ство­вал в со­от­вет­ствии с этой стра­те­ги­ей, то вто­рая клет­ка до­ми­нош­ки не за­кра­ше­на и сде­лать в неё ход можно. Оче­вид­но, что по­след­ний ход сде­ла­ет Да­ни­ла  — хотя бы по­то­му, что он все­гда может сде­лать ход.

Ответ: Данил вы­иг­ры­ва­ет.

До­ка­жем тре­бу­е­мое утвер­жде­ние ин­дук­ци­ей по ко­ли­че­ству гно­мов.

База  — один гном; утвер­жде­ние оче­вид­но.

Шаг  — пусть утвер­жде­ние верно для лю­бо­го клана из n гно­мов, до­ка­жем его для лю­бо­го клана из n + 1 гно­мов.

Рас­смот­рим про­из­воль­ный клан из n + 1 гно­мов и то, как они ме­ня­лись мо­не­та­ми. Пусть a_ij  — число монет у гнома номер i на в день номер j. Среди всех чисел a_ij есть мак­си­маль­ное  — так как все a_ij на­ту­раль­ны и огра­ни­че­ны свер­ху сум­мар­ным ко­ли­че­ством монет в клане. Пусть a_kp  — одно из мак­си­маль­ных чисел. Тогда, на­чи­ная с дня номер p, гном номер k не будет ни­ко­му да­вать мо­не­ты и ни у кого по­лу­чать мо­не­ты. Дей­стви­тель­но: гном номер k может от­дать мо­не­ты, толь­ко если найдётся гном, у ко­то­ро­го боль­ше монет. А та­ко­го гнома ни­ко­гда не найдётся из мак­си­маль­но­сти a_kp. Гном номер k не может по­лу­чить мо­не­ты, по­то­му что если ему кто-то от­даст мо­не­ты, то число монет у гнома номер k ста­нет боль­ше a_kp, что так же про­ти­во­ре­чит мак­си­маль­но­сти a_kp.

На­чи­ная со дня номер p, будем рас­смат­ри­вать всех гно­мов, кроме гнома с но­ме­ром k, как клан из n гно­мов. Это кор­рект­но, так как они не по­лу­ча­ют и не от­да­ют мо­не­ты гному с но­ме­ром k. По пред­по­ло­же­нию ин­дук­ции, на­чи­ная с ка­ко­го-то дня, гномы в этом новом клане пе­ре­ста­нут пе­ре­да­вать друг другу мо­не­ты, что и тре­бо­ва­лось до­ка­зать.

Вы­де­лим не­ко­то­рые вер­ши­ны графа, об­ве­дя их в кру­жо­чек. Из­на­чаль­но, один из ав­то­мо­би­лей на­хо­дит­ся в вы­де­лен­ной вер­ши­не, а вто­рой нет. Из вы­де­лен­ной вер­ши­ны можно по­пасть толь­ко в не­вы­де­лен­ную и на­о­бо­рот (дву­доль­ный граф). По­это­му в одной вер­ши­не ав­то­мо­би­ли ока­зать­ся не могут.

Пусть пер­вая ча­сти­ца пры­га­ет через s сто­рон по ча­со­вой стрел­ке, вто­рая  — через t сто­рон про­тив ча­со­вой стрел­ки. Пер­во­на­чаль­но пер­вая ча­сти­ца на­хо­дит­ся на рас­сто­я­нии d сто­рон по ча­со­вой стрел­ке от вто­рой. Пе­рей­дем в си­сте­му от­сче­та, свя­зан­ную со вто­рой ча­сти­цей. То есть, вто­рая ча­сти­ца не­по­движ­на, а пер­вая со­вер­ша­ет прыж­ки через ребер по ча­со­вой стрел­ке. За­ме­тим, что рас­сто­я­ние между ча­сти­ца­ми, от­счи­ты­ва­е­мое по ча­со­вой стрел­ке от пер­вой ко вто­рой, со­став­ля­ет сто­рон. За­ну­ме­ру­ем вер­ши­ны мно­го­уголь­ни­ка це­лы­ми чис­ла­ми от 0 до 2015 таким об­ра­зом, что пер­во­на­чаль­но пер­вая ча­сти­ца на­хо­дит­ся в вер­ши­не с но­ме­ром 0, а вто­рая  — в вер­ши­не с но­ме­ром Пусть n  — ис­ко­мое ко­ли­че­ство прыж­ков. Тогда, чтобы пер­вая ча­сти­ца по­па­ла в вер­ши­ну долж­но вы­пол­нять­ся со­от­но­ше­ние

Итак, надо найти на­ту­раль­ное n, для ко­то­ро­го су­ще­ству­ет на­ту­раль­ное k такое, что

Число 2016 дает оста­ток 3 при де­ле­нии на 183. Сле­до­ва­тель­но, чтобы чис­ли­тель давал оста­ток ноль при де­ле­нии на 183, до­ста­точ­но взять Тогда

Ответ: 165.

Разо­бьем от­ре­зок от 0 до 1 на 1000 оди­на­ко­вых по­до­т­рез­ков и от­ме­тим на нем точки Здесь фи­гур­ные скоб­ки обо­зна­ча­ют дроб­ную часть числа. В силу того, что число ир­ра­ци­о­наль­но, ни одна точка x_i не может сов­пасть с кон­цом по­до­т­рез­ка. Ясно также, что если хоть одна из этих точек по­па­ла на по­до­т­ре­зок, от­ме­чен­ный серым, то наше утвер­жде­ние до­ка­за­но. По­это­му пред­по­ло­жим, что ни одна точка на эти край­ние по­до­т­рез­ки не по­па­ла. Тогда по­лу­ча­ет­ся, что наши 999 точек долж­ны раз­ме­стить­ся на 998 остав­ших­ся по­до­т­рез­ках. Зна­чит, су­ще­ству­ет хотя бы один по­до­т­ре­зок, внутрь ко­то­ро­го по­па­дут по край­ней мере две точки x_m и Тогда Утвер­жде­ние до­ка­за­но.

Пусть пер­вая ча­сти­ца пры­га­ет через s сто­рон по ча­со­вой стрел­ке, вто­рая  — через t сто­рон про­тив ча­со­вой стрел­ки. Пер­во­на­чаль­но пер­вая ча­сти­ца на­хо­дит­ся на рас­сто­я­нии d сто­рон по ча­со­вой стрел­ке от вто­рой. Пе­рей­дем в си­сте­му от­сче­та, свя­зан­ную со вто­рой ча­сти­цей. То есть, вто­рая ча­сти­ца не­по­движ­на, а пер­вая со­вер­ша­ет прыж­ки через ребер по ча­со­вой стрел­ке. За­ме­тим, что рас­сто­я­ние между ча­сти­ца­ми, от­счи­ты­ва­е­мое по ча­со­вой стрел­ке от пер­вой ко вто­рой, со­став­ля­ет сто­рон. За­ну­ме­ру­ем вер­ши­ны мно­го­уголь­ни­ка це­лы­ми чис­ла­ми от 0 до 2015 таким об­ра­зом, что пер­во­на­чаль­но пер­вая ча­сти­ца на­хо­дит­ся в вер­ши­не с но­ме­ром 0, а вто­рая  — в вер­ши­не с но­ме­ром Пусть n  — ис­ко­мое ко­ли­че­ство прыж­ков. Тогда, чтобы пер­вая ча­сти­ца по­па­ла в вер­ши­ну долж­но вы­пол­нять­ся со­от­но­ше­ние

Итак, надо найти на­ту­раль­ное n, для ко­то­ро­го су­ще­ству­ет на­ту­раль­ное k такое, что

Число 2016 дает оста­ток 3 при де­ле­нии на 183. Сле­до­ва­тель­но, чтобы чис­ли­тель давал оста­ток ноль при де­ле­нии на 183, до­ста­точ­но взять Тогда

Ответ: 165.

Если в каж­дой стро­ке не боль­ше двух раз­лич­ных букв, то общее их число не пре­вос­хо­дит 10  =  5 · 2. Далее можно счи­тать, что в пер­вой стро­ке ровно три раз­лич­ных буквы. Если каж­дая из остав­ших­ся строк имеет хотя бы одну общую букву с пер­вой, то общее число букв не пре­вос­хо­дит 3 + 4 · 2  =  11. Пусть име­ет­ся стро­ка, можно счи­тать, вто­рая, в ко­то­рой три раз­лич­ных буквы, от­лич­ных от букв пер­вой стро­ки. Тогда в каж­дом столб­це кроме букв пер­вой и вто­рой строк может быть не более одной новой буквы, всего не более 3 + 3 + 5 · 1  =  11.

При­мер рас­ста­нов­ки 11 раз­лич­ных букв: по глав­ной диа­го­на­ли таб­ли­цы из ле­во­го ниж­не­го угла в пра­вый верх­ний за­пи­са­ны пер­вые пять раз­лич­ных букв, по со­сед­ней снизу диа­го­на­ли  — сле­ду­ю­щие че­ты­ре, в левом верх­нем углу  — де­ся­тая, а в осталь­ных клет­ках  — один­на­дца­тая буквы.

Ответ: 11.

До­ка­жем ме­то­дом ма­те­ма­ти­че­ской ин­дук­ции. При   — оче­вид­но. В про­из­воль­ном слове w от n + 1 буквы рас­смот­рим первую слева букву, назовём её a, если она боль­ше не встре­ча­ет­ся в w, остав­ша­я­ся часть w яв­ля­ет­ся сло­вом от n букв и по пред­по­ло­же­нию ин­дук­ции имеет длину не боль­ше Общая длина w при этом не пре­вос­хо­дит

Если a встре­ча­ет­ся в w ещё хотя бы раз, то под­сло­ва, на ко­то­рые a раз­би­ва­ет w, не имеют общих букв. Иначе, убрав всё, кроме пер­вой a, буквы b, встре­ча­ю­щей­ся в раз­ных под­сло­вах и вто­рой буквы a, сто­я­щей между этими b, по­лу­чим слово abab, за­прещённое усло­ви­ем. Пусть всего w со­дер­жит k вхож­де­ний a, оно раз­би­ва­ет w на k (если по­след­няя буква w не a) или k − 1 (если по­след­няя буква w равна a) под­слов, каж­дое из ко­то­рых ис­поль­зу­ет не­пе­ре­се­ка­ю­ще­е­ся с дру­ги­ми мно­же­ство букв. Длина каж­до­го под­сло­ва оце­ни­ва­ет­ся по ин­дук­ции как удво­ен­ное число ис­поль­зо­ван­ных в нём раз­лич­ных букв, умень­шен­ное на 1. Всего в этих сло­вах за­дей­ство­ван­но n букв, по­это­му общая сум­мар­ная длина всех под­слов не пре­вос­хо­дит До­бав­ля­ем сюда k вхож­де­ний a, по­лу­чим, что длина w не пре­вос­хо­дит   — шаг ин­дук­ции до­ка­зан.

Ответ:

Про­ве­дем ре­ше­ние ин­дук­ци­ей по ко­ли­че­ству участ­ни­ков кон­фе­рен­ции. База ин­дук­ции про­ве­ря­ет­ся не­по­сред­ствен­но.

Пред­по­ло­жим, что для n участ­ни­ков утвер­жде­ние за­да­чи верно.

Пусть на кон­фе­рен­цию при­е­ха­ли n + 1 участ­ни­ков. Если каж­дый из них имеет чет­ное число зна­ко­мых, что можно оста­вить одну из ком­нат пу­стой и тре­бо­ва­ние за­да­чи будет вы­пол­не­но. По­это­му будем счи­тать, что не­ко­то­рый участ­ник А имеет нечётное ко­ли­че­ство зна­ко­мых B₁, B₂, …, B_{2k + 1}. По­про­сим участ­ни­ка A на время уда­лить­ся с кон­фе­рен­ции. Кроме того, за­ста­вим любых двух его зна­ко­мых по­зна­ко­мить­ся между собой, если они пре­жде не были зна­ко­мы, и, на­про­тив, вре­мен­но пре­рвать зна­ком­ство, если они знали друг друга. По­лу­чен­ную ком­па­нию из n че­ло­век можно, по пред­по­ло­же­нию ин­дук­ции, раз­ме­стить в двух ком­на­тах так, чтобы у каж­до­го было чет­ное число зна­ко­мых в своей ком­на­те. Не ума­ляя общ­но­сти, можно счи­тать, что участ­ни­ки B₁, B₂, …, B_2s по­па­ли в первую ком­на­ту, а B_{2s + 1}, B_{2s + 2}, …, B_{2k + 1}  — во вто­рую (). Те­перь по­зо­вем об­рат­но из­гнан­но­го A и под­се­лим его в первую ком­на­ту  — он будет знать

там чет­ное число людей. При этом ко­ли­че­ство зна­ко­мых у участ­ни­ков B₁, B₂, …, B_2s ста­нет не­чет­ным. На­ко­нец, вер­нем все зна­ком­ства между B_i () в пер­во­на­чаль­ное со­сто­я­ние. Каж­дое при­об­ре­тен­ное или по­те­рян­ное зна­ком­ство ме­ня­ет ко­ли­че­ство зна­ко­мых на еди­ни­цу. По­это­му у каж­до­го из B₁, B₂, …, B_2s ко­ли­че­ство зна­ко­мых среди людей этого на­бо­ра по­ме­ня­ет чет­ность (и ста­нет чет­ным), а у каж­до­го из B_{2s + 1}, B_{2s + 2}, …, B_{2k + 1} по-преж­не­му оста­нет­ся чет­ным. У дру­гих участ­ни­ков, кроме A и B_i, на­бо­ры зна­ко­мых всё это время во­об­ще не ме­ня­лись. По­это­му по­лу­чен­ное раз­ме­ще­ние всех участ­ни­ков по двум ком­на­там удо­вле­тво­ря­ет усло­вию за­да­чи.

Каж­дый уче­ник вы­пол­ня­ет пе­ре­ста­нов­ку: если он кого-то не­до­люб­ли­ва­ет, то пе­ре­ста­нов­ку, ме­ня­ю­щую его имя и имя того, кого он не­до­люб­ли­ва­ет; иначе пе­ре­ста­нов­ка три­ви­аль­на. Дру­ги­ми сло­ва­ми, ни­ка­кие два имени не ста­нут оди­на­ко­вы­ми после про­хож­де­ния лю­бо­го из уче­ни­ков. И для каж­до­го имени в ре­зуль­та­те есть имя, ко­то­рое при­ве­ло бы к та­ко­му ре­зуль­та­ту. Раз это утвер­жде­ние верно для лю­бо­го от­дель­но­го уче­ни­ка, это же тре­бо­ва­ние верно и для по­сле­до­ва­тель­но­сти уче­ни­ков. Таким об­ра­зом, зная, какое имя долж­но прий­ти в итоге и кто кого не­до­люб­ли­ва­ет, для каж­до­го уче­ни­ка из­вест­на вы­пол­ня­е­мая им пе­ре­ста­нов­ка. Таким об­ра­зом, для каж­до­го уче­ни­ка можно по ре­зуль­та­ту пе­ре­ста­нов­ки, ко­то­рый он дол­жен по­лу­чить, найти, какое имя долж­но было ему прий­ти. Таким об­ра­зом, в об­рат­ном на­прав­ле­нии по це­поч­ке вос­ста­нав­ли­ва­ет­ся, какое имя сле­ду­ет на­пи­сать из­на­чаль­но.

Ответ: сколь­ко угод­но.

Усло­вия за­да­чи тре­бу­ют, чтобы мышь про­грыз­ла каж­дую ко­роб­ку как ми­ни­мум в двух ме­стах: чтобы по­пасть в нее и чтобы по­ки­нуть её. Таким об­ра­зом, число от­вер­стий не мень­ше удво­ен­но­го числа ко­ро­бок, то есть 2 · (8ⁿ⁺¹ − 1) / 7. По­стро­им путь мыши с таким чис­лом от­вер­стий, при­чем вовсе без ко­ро­бок с про­гры­зен­ны­ми про­ти­во­по­лож­ны­ми стен­ка­ми. Мы будем со­став­лять его из сле­ду­ю­щих ку­соч­ков:

Дан­ный ри­су­нок изоб­ра­жа­ет спо­соб по­се­тить все ко­роб­ки раз­ме­ра 1 дм внут­ри одной ко­роб­ки раз­ме­ра 2 дм, про­гры­зя за­штри­хо­ван­ные места. За­ме­тим, что каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Если те­перь мы обойдём все ко­роб­ки раз­ме­ра 2 дм в дан­ной ко­роб­ке раз­ме­ра 4 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2 дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 4 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. И так далее: если обой­ти все ко­роб­ки раз­ме­ра 2^k дм в дан­ной ко­роб­ке раз­ме­ра 2^k+1 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2^k дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 2^k+1 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Чтобы в ре­зуль­та­те по­лу­чить за­мкну­тый путь внут­ри сун­ду­ка, ко­роб­ки раз­ме­ра 2ⁿ⁻¹ можно обой­ти по сле­ду­ю­щей схеме:

Те­перь, в какой бы ко­роб­ке этого за­мкну­то­го пути ни за­ве­лась мышь, она смо­жет про­сле­до­вать по этому пути, по­бы­вав ровно один раз в каж­дой ко­роб­ке, вер­нув­шись в из­на­чаль­ную, и сде­лав ровно по од­но­му от­вер­стию в двух со­сед­них стен­ках каж­дой ко­роб­ки.

Ответ: 2 · (8ⁿ⁺¹ − 1) / 7.

Пусть a₁  — ко­ли­че­ство зо­ло­тых монет у пер­во­го пи­ра­та, a₂  — у вто­ро­го, и т. д. Так как a_i-a_j не де­лит­ся на 10 для любых i и j, то числа a₁, a₂, …,a₁₀ долж­ны да­вать раз­лич­ные остат­ки при де­ле­нии на 10. За­пи­шем a_i = 10k_i + l_i, где l_i  — оста­ток a_i при де­ле­нии на 10. Общее ко­ли­че­ство зо­ло­тых монет равно

Так как числа l₁, ..., l₁₀  — в точ­но­сти числа 0, 1, 2, ..., 9 (толь­ко не обя­за­тель­но в таком по­ряд­ке), то их сумма равна 45. Зна­чит, всего зо­ло­тых монет 10(k₁ + k₂ + ... + k₁₀) + 45. Пред­по­ло­жим, что пи­ра­ты могут раз­де­лить се­реб­ря­ные мо­не­ты таким же об­ра­зом. Как и рань­ше мы можем по­ка­зать, что общее ко­ли­че­ство се­реб­ря­ных монет 10(m₁ + m₂ + ... + m₁₀) + 45 для не­ко­то­рых целых чисел m₁, m₂, ..., m₁₀. Но общее число се­реб­ря­ных монет четно, по­лу­ча­ем про­ти­во­ре­чие.

Легко по­нять, что если точка яв­ля­ет­ся кон­цом для хотя бы одной сто­ро­ны ше­сти­уголь­ни­ка, она яв­ля­ет­ся кон­цом для двух или для трёх сто­рон: боль­ше, чем 3, быть не может по­то­му что все углы равны 120°.

Да­вай­те не­мно­го по­ри­су­ем. Пред­ста­вим себе, что в каж­дую точку, яв­ля­ю­щу­ю­ся кон­цом для трёх сто­рон ше­сти­уголь­ни­ка, мы по­ста­ви­ли точку крас­ным фло­ма­сте­ром. А каж­дый путь по сто­ро­нам ше­сти­уголь­ни­ков от крас­ной точки до крас­ной точки мы об­ве­ли синим фло­ма­сте­ром. Таким об­ра­зом, синие линии идут по сто­ро­нам ше­сти­уголь­ни­ков и через вер­ши­ны, из ко­то­рых вы­хо­дит толь­ко две сто­ро­ны (иными сло­ва­ми, ко­то­рые яв­ля­ют­ся вер­ши­на­ми ровно для од­но­го ше­сти­уголь­ни­ка). За­ме­тим, что синие линии не пе­ре­се­ка­ют­ся иначе, чем в своих кон­цах, яв­ля­ю­щих­ся крас­ны­ми точ­ка­ми. Легко по­нять, что если точка яв­ля­ет­ся кон­цом для хотя бы одной сто­ро­ны ше­сти­уголь­ни­ка, она яв­ля­ет­ся кон­цом для двух или для трёх сто­рон: боль­ше чем 3 быть не может по­то­му что все углы равны 120°.

Таким об­ра­зом, мы по­лу­чи­ли изоб­ра­же­ние муль­ти­гра­фа на плос­ко­сти. Для него верна фор­му­ла Эй­ле­ра F − E + V  =  2, где F, E, V  — ко­ли­че­ства гра­ней, рёбер и вер­шин со­от­вет­ствен­но. По­сколь­ку все вер­ши­ны имеют сте­пень 3, 3V  =  2E. Кроме того F = n + 1, по­сколь­ку это все ше­сти­уголь­ни­ки и внеш­няя грань. Из этих трёх урав­не­ний вы­во­дит­ся E  =  3n − 3. Пройдём по внеш­не­му циклу. При этом мы шли по всем n ше­сти­уголь­ни­кам, зна­чит, при n > 1 не менее чем n раз ме­ня­ли ше­сти­уголь­ник, по ко­то­ро­му идем (вни­ма­ние: этот утвер­жде­ние не­вер­но, если n = 1: так и хо­ди­ли по од­но­му ше­сти­уголь­ни­ку, ни разу его не по­ме­няв). Зна­чит, во внеш­нем цикле не менее n ребер, зна­чит, в осталь­ном графе не боль­ше 2n − 3 рёбер. Каж­дое из них со­сто­ит ровно из од­но­го от­рез­ка, быв­ше­го сто­ро­ной для двух ше­сти­уголь­ни­ков, по­сколь­ку внут­ри мно­го­уголь­ни­ка не может быть точек, яв­ля­ю­щих­ся кон­ца­ми ровно для двух от­рез­ков сто­рон. Зна­чит, внут­ри не боль­ше 4n − 6 сто­рон ше­сти­уголь­ни­ков, скле­ен­ных по парам, зна­чит, на гра­ни­це лежит не менее 2n + 6 сто­рон.

Ответ: 2n + 6 при n ≥ 2, 6 при n = 1

Каж­дый уче­ник вы­пол­ня­ет пе­ре­ста­нов­ку: если он кого-то не­до­люб­ли­ва­ет, то пе­ре­ста­нов­ку, ме­ня­ю­щую его имя и имя того, кого он не­до­люб­ли­ва­ет; иначе пе­ре­ста­нов­ка три­ви­аль­на. Дру­ги­ми сло­ва­ми, ни­ка­кие два имени не ста­нут оди­на­ко­вы­ми после про­хож­де­ния лю­бо­го из уче­ни­ков. И для каж­до­го имени в ре­зуль­та­те есть имя, ко­то­рое при­ве­ло бы к та­ко­му ре­зуль­та­ту. Раз это утвер­жде­ние верно для лю­бо­го от­дель­но­го уче­ни­ка, это же тре­бо­ва­ние верно и для по­сле­до­ва­тель­но­сти уче­ни­ков. Таким об­ра­зом, зная, какое имя долж­но прий­ти в итоге и кто кого не­до­люб­ли­ва­ет, для каж­до­го уче­ни­ка из­вест­на вы­пол­ня­е­мая им пе­ре­ста­нов­ка. Таким об­ра­зом, для каж­до­го уче­ни­ка можно по ре­зуль­та­ту пе­ре­ста­нов­ки, ко­то­рый он дол­жен по­лу­чить, найти, какое имя долж­но было ему прий­ти. Таким об­ра­зом, в об­рат­ном на­прав­ле­нии по це­поч­ке вос­ста­нав­ли­ва­ет­ся, какое имя сле­ду­ет на­пи­сать из­на­чаль­но.

Ответ: сколь­ко угод­но.

Усло­вия за­да­чи тре­бу­ют, чтобы мышь про­грыз­ла каж­дую ко­роб­ку как ми­ни­мум в двух ме­стах: чтобы по­пасть в нее и чтобы по­ки­нуть её. Таким об­ра­зом, число от­вер­стий не мень­ше удво­ен­но­го числа ко­ро­бок, то есть 2 · (8ⁿ⁺¹ − 1) / 7. По­стро­им путь мыши с таким чис­лом от­вер­стий, при­чем вовсе без ко­ро­бок с про­гры­зен­ны­ми про­ти­во­по­лож­ны­ми стен­ка­ми. Мы будем со­став­лять его из сле­ду­ю­щих ку­соч­ков:

Дан­ный ри­су­нок изоб­ра­жа­ет спо­соб по­се­тить все ко­роб­ки раз­ме­ра 1 дм внут­ри одной ко­роб­ки раз­ме­ра 2 дм, про­гры­зя за­штри­хо­ван­ные места. За­ме­тим, что каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Если те­перь мы обойдём все ко­роб­ки раз­ме­ра 2 дм в дан­ной ко­роб­ке раз­ме­ра 4 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2 дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 4 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. И так далее: если обой­ти все ко­роб­ки раз­ме­ра 2^k дм в дан­ной ко­роб­ке раз­ме­ра 2^k+1 дм в том же по­ряд­ке и с от­вер­сти­я­ми в тех же ме­стах, как по­ка­за­но на ри­сун­ке, об­хо­дя при этом каж­дую ко­роб­ку раз­ме­ра 2^k дм опи­сан­ным спо­со­бом, то по­лу­чим обход ко­роб­ки раз­ме­ра 2^k+1 дм, при ко­то­ром каж­дая из за­дей­ство­ван­ных ко­ро­бок про­гры­за­ет­ся ровно в двух ме­стах, и ни у одной не про­гры­зе­ны про­ти­во­по­лож­ные стен­ки. Чтобы в ре­зуль­та­те по­лу­чить за­мкну­тый путь внут­ри сун­ду­ка, ко­роб­ки раз­ме­ра 2ⁿ⁻¹ можно обой­ти по сле­ду­ю­щей схеме:

Те­перь, в какой бы ко­роб­ке этого за­мкну­то­го пути ни за­ве­лась мышь, она смо­жет про­сле­до­вать по этому пути, по­бы­вав ровно один раз в каж­дой ко­роб­ке, вер­нув­шись в из­на­чаль­ную, и сде­лав ровно по од­но­му от­вер­стию в двух со­сед­них стен­ках каж­дой ко­роб­ки.

Ответ: 2 · (8ⁿ⁺¹ − 1) / 7.